package cn.njupt;

import cn.njupt.printer.BinaryTreeInfo;

import java.util.Comparator;

public class BinaryHeap<E> implements Heap<E>, BinaryTreeInfo {

    private int size;

    private E[] elements;

    private Comparator comparator;

    public static final int DEFAULT_CAPACITY=10;


    public BinaryHeap(){
        this(null,null);
    }

    public BinaryHeap(E[] exterElements,Comparator comparator){
        this.comparator=comparator;
        if(exterElements==null || exterElements.length==0){
            this.elements=(E[])new Object[DEFAULT_CAPACITY];
        }else{
            int capacity=Math.max(DEFAULT_CAPACITY,exterElements.length);
            this.elements=(E[])new Object[capacity];
            this.size= exterElements.length;
            for (int i = 0; i < exterElements.length; i++) {
                this.elements[i]=exterElements[i];
            }
            //批量建堆，调整堆
            heapify();
        }
    }

    public BinaryHeap(E[] exterElements){
        this(exterElements,null);
    }
    public BinaryHeap(Comparator comparator){
        this(null,comparator);
    }

    private void heapify() {
        for (int i = (size>>1)-1; i >=0 ; i--) {
            siftDown(i);
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void add(E element) {
        elementIsNullCheck(element);
        ensureCapacity(size+1);
        //上滤
        elements[size++]=element;
        siftUp(size-1);
    }

    public void siftUp(int index){
        E initalElement=elements[index];
        while(index>0){
            int parentIndex=(index-1)>>1;
            E parentElement=elements[parentIndex];
            if(compare(parentElement,initalElement)>=0)break;

            elements[index]=parentElement;
            index=parentIndex;
        }
        elements[index]=initalElement;
    }


    public int compare(E e1,E e2){
        if(comparator!=null){
            return comparator.compare(e1,e2);
        }
        return ((Comparable)e1).compareTo(e2);
    }


    private void ensureCapacity(int capacity) {
        int oldCapacity=this.elements.length;
        if(capacity<=oldCapacity)return;

        //进行扩容1.5倍
        int newCapacity=oldCapacity+(oldCapacity>>1);

        E[] newElements=(E[])new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i]=this.elements[i];
        }
        this.elements=newElements;
    }

    /**
     * 删除第一个元素并且返回
     * @return
     */
    @Override
    public E remove() {
        elementsEmptyCheck();
        E top=elements[0];
        int lastIndex=--size;
        elements[0]=elements[lastIndex];
        elements[lastIndex]=null;
        siftDown(0);
        return top;
    }

    /**
     * 下滤
     * @param index
     */
    private void siftDown(int index) {
        int half=size>>1;
        E initalElement=elements[index];
        while(index<half){
            //默认初始值设为左节点
            int childIndex=(index<<1)+1;

            E child=elements[childIndex];

            int rightIndex=childIndex+1;

            if(rightIndex<size && compare(elements[rightIndex],child)>0){
                child=elements[childIndex=rightIndex];
            }

            if(compare(child,initalElement)<=0)break;

            //说明孩子节点值大
            elements[index]=child;
            index=childIndex;
        }
        elements[index]=initalElement;
    }

    /**
     * 替换首节点，并且调整堆
     * @param element
     * @return
     */
    @Override
    public E replace(E element) {
        elementIsNullCheck(element);
        E top=null;
        if(size==0){
            elements[size++]=element;
        }else{
            top=elements[0];
            elements[0]=element;
            siftDown(0);
        }
        return top;
    }

    @Override
    public E get() {
        elementsEmptyCheck();
        return elements[0];
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            this.elements[i]=null;
        }
        size=0;
    }

    public void elementIsNullCheck(E element){
        if(element==null){
            throw new IllegalArgumentException("元素不能为null");
        }

    }
    public void elementsEmptyCheck(){
        if(size==0){
            throw new IndexOutOfBoundsException("堆中没有元素");
        }
    }

    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {
        int index=((int)node<<1)+1;
        return index<size?index:null;
    }

    @Override
    public Object right(Object node) {
        int index=((int)node<<1)+2;
        return index<size?index:null;
    }

    @Override
    public Object string(Object node) {
        return (elements[(int)node]);
    }
}
